#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

 

示例 :
给定二叉树

          1
         / \
        2   3
       / \
      4   5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*
* */

// 返回最长路径长度
// left+right+ root
//同 142
int res = 0;

int diameterOfBinaryTree_r(TreeNode *root) {
    if (root == nullptr)
        return 0;

    int left = diameterOfBinaryTree_r(root->left);
    int right = diameterOfBinaryTree_r(root->right);
    res = max(res, left + right);//按照我的意思这边是lef+right+1 为什么没加根节点的 奥我草其实是加了
    //因为线的长度和个数是差了1
    return max(left, right) + 1;

}

int diameterOfBinaryTree(TreeNode *root) {
    diameterOfBinaryTree_r(root);
    return res;
}